import random
import math

class Particle:
    def __init__(self, cities):
        self.cities = cities
        self.num_cities = len(cities)
        self.position = random.sample(range(self.num_cities), self.num_cities)
        self.velocity = [random.randint(-5, 5) for _ in range(self.num_cities)]
        self.best_position = self.position.copy()
        self.best_fitness = self.calculate_fitness()

    def calculate_fitness(self):
        total_distance = 0
        for i in range(self.num_cities):
            from_city = self.position[i]
            to_city = self.position[(i + 1) % self.num_cities]
            total_distance += math.sqrt((self.cities[from_city][0] - self.cities[to_city][0])**2 + (self.cities[from_city][1] - self.cities[to_city][1])**2)
        return total_distance

    def update_position(self):
        for i in range(self.num_cities):
            self.position[i] = (self.position[i] + self.velocity[i]) % self.num_cities

    def update_velocity(self, global_best_position):
        w = 0.5
        c1 = 1.5
        c2 = 1.5
        for i in range(self.num_cities):
            r1 = random.random()
            r2 = random.random()
            cognitive_component = c1 * r1 * (self.best_position[i] - self.position[i])
            social_component = c2 * r2 * (global_best_position[i] - self.position[i])
            self.velocity[i] = w * self.velocity[i] + cognitive_component + social_component

class ParticleSwarmOptimization:
    def __init__(self, num_particles, cities):
        self.num_particles = num_particles
        self.particles = [Particle(cities) for _ in range(num_particles)]
        self.global_best_position = None
        self.global_best_fitness = float('inf')

    def update_global_best(self):
        for particle in self.particles:
            if particle.best_fitness < self.global_best_fitness:
                self.global_best_fitness = particle.best_fitness
                self.global_best_position = particle.best_position.copy()

    def run(self):
        iterations = 100
        for _ in range(iterations):
            for particle in self.particles:
                particle.update_position()
                new_fitness = particle.calculate_fitness()
                if new_fitness < particle.best_fitness:
                    particle.best_fitness = new_fitness
                    particle.best_position = particle.position.copy()
            self.update_global_best()
            for particle in self.particles:
                particle.update_velocity(self.global_best_position)
        return self.global_best_position, self.global_best_fitness

# 示例用法
cities = [(0, 0), (1, 2), (3, 1), (5, 3), (2, 5)]
pso = ParticleSwarmOptimization(10, cities)
best_path, best_distance = pso.run()
print("Best path:", best_path)
print("Best distance:", best_distance)